# 顺序查找算法
# 特点: 不需要待查找的列表有序
def sequentialSearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos += 1
    return found


# print(sequentialSearch([1, 2, 32, 8, 17, 19, 42, 13], 13))

# 对有序列表的顺序查找
# 在无序表的基础上, 可以改进找不到的效率
# 当某一项大于待查找元素时, 即可停止查找
def orderedSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        elif alist[pos] > item:
            stop = True
        else:
            pos += 1
    return found

# print(orderedSequentialSearch([1,3, 8, 11, 56, 78], 9))

# 二分查找算法
# 针对顺序列表


def binarySearch(alist, item):
    low = 0
    high = len(alist)
    mid = (low+high)//2
    found = False

    while low < high and not found:
        if alist[mid] == item:
            found = True
        elif alist[mid] < item:
            low = mid + 1
        else:
            high = mid - 1
        mid = (low + high)//2
    return found

# 二分查找的递归算法
def binaryCurSearch(alist, item):
    if len(alist)==0:
        return False
    else:
        mid = len(alist)//2
        if alist[mid] == item:
            return True
        elif alist[mid] > item:
            return binaryCurSearch(alist[:mid], item)
        else:
            return binaryCurSearch(alist[mid+1:], item)

print(binaryCurSearch([1, 3, 8, 11, 56, 78],6))
